437. 路径总和 III
题目: 437. 路径总和 III
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例1:
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。
示例2:
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3
提示
- 二叉树的节点个数的范围是 [0,1000]
- $-10^9$ <= Node.val <= $10^9$
-1000 <= targetSum <= 1000
题解: 穷举 深度优先搜索
因为 路径 必须是向下的， 即只能从父节点到子节点，我们可以借助递归遍历来得到 当前节点 到 以递归节点的 totalNum，通过判断 tatolNum 与 targetNum 值 来增加路径总数，并且返回路径总数。
我们递归遍历每一个节点的所有可能的路径，然后将这些路径数目加起来即为返回结果。
首先定义 $\textit{rootSum}(p,\textit{val})$ 表示 以节点 p 为起点向下且满足路径总和为targetNum的路径数目。我们对二叉树上每个节点 p 求出 $\textit{rootSum}$，然后对这些路径数目求和即为返回结果。
细节
我们对节点 p 求 $\textit{rootSum}(p,\textit{targetSum})$ 时，以当前节点 p 为目标路径的起点递归向下进行搜索。
假设当前的节点 p 的值为 $\textit{val}$，我们对左子树和右子树进行递归搜索，
- 对节点 p 的左孩子节点 $p_{l}$求出 $\textit{rootSum}(p_{l},\textit{targetSum}-\textit{val})$
- 对节点 p 的右孩子节点 $p_{r}$求出 $\textit{rootSum}(p_{r},\textit{targetSum}-\textit{val})$
- 节点 p 的 $\textit{rootSum}(p,\textit{targetSum})$ 即等于 $\textit{rootSum}(p_{l},\textit{targetSum}-\textit{val})$ 与 $\textit{rootSum}(p_{r},\textit{targetSum}-\textit{val})$ 之和，同时我们还需要判断一下当前节点 p 的值是否刚好等于 $\textit{targetSum}$。
代码
const rootSum = (root, targetNum)=>{
if(root === null) return 0
let ret = 0
if(root.val === targetNum) ret++
ret += rootSum(root.left, targetNum - root.val)
ret += rootSum(root.right, targetNum - root.val)
return ret
}
var pathSum = function(root, targetSum) {
if(root === null) return 0
let ret = rootSum(root,targetSum)
// 递归调用左节点
ret += pathSum(root.left,targetSum)
// 递归调用右节点
ret += pathSum(root.right,targetSum)
return ret
};
题解 2: 前缀和 深度优先遍历
题解1的遍历，可以很明显的看出有大量的重复计算，而这些重复计算，在这里可以使用 前缀和 + 回溯 来代替。
我们定义节点的前缀和：从根结点到当前结点的路径上所有节点的和。
细节
我们通过先序遍历得到从根节点到当前节点的路径中所有节点的前缀和，在已保存的路径前缀和中查找是否存在前缀和刚好等于当前节点到根节点的前缀和 currcurr 减去 $\textit{targetSum}$。
-
对于空路径我们也需要保存预先处理一下，此时因为空路径不经过任何节点，因此它的前缀和为 0。
-
假设根节点为 $\textit{root}$，我们当前刚好访问节点 $\textit{node}$，则此时从根节点 $\textit{root}$ 到节点 $\textit{node}$ 的路径（无重复节点）刚好为 $\textit{root} \rightarrow p_1 \rightarrow p_2 \rightarrow \ldots \rightarrow p_k \rightarrow \textit{node}$，此时我们可以已经保存了节点 $p_1, p_2, p_3, \ldots, p_k$的前缀和，并且计算出了节点 $\textit{node}$ 的前缀和。
-
假设当前从根节点 $\textit{root}$ 到节点 $\textit{node}$ 的前缀和为 $\textit{curr}$，则此时我们在已保存的前缀和查找是否存在前缀和刚好等于 $\textit{curr} - \textit{targetSum}$。假设从根节点 $\textit{root}$ 到节点 $\textit{node}$ 的路径中存在节点 $p_i$到根节点 $\textit{root}$ 的前缀和为 $\textit{curr} - \textit{targetSum}$，则节点 $p_{i+1}$ 到 $\textit{node}$ 的路径上所有节点的和一定为 $\textit{targetSum}$。
-
我们利用深度搜索遍历树，当我们退出当前节点时，我们需要及时更新已经保存的前缀和。
代码
var pathSum = function(root, targetSum) {
if(root === null) return 0
let ret = rootSum(root,targetSum)
// 递归调用左节点
ret += pathSum(root.left,targetSum)
// 递归调用右节点
ret += pathSum(root.right,targetSum)
return ret
};
const dfs=(root, prefix, curr, targetSum)=>{
if(root===null) return 0
let ret = 0
curr += root.val
ret = prefix.set()
}